Throughout the instant disclosure, numerals in brackets—[ ]—are keyed to the list of numbered references towards the end of the disclosure.
A growing number of applications are using overlay network support to provide a variety of value added services in the Internet, e.g., CDN (Content Delivery Network) based services, collaborative applications such as video conferencing, instant messaging, secure network services. Typically in an overlay based communication, a forwarding tree is constructed using participating end-system devices and (optionally) forwarding servers to distribute content. This has been advocated as a practical alternative architecture to IP-multicast for supporting large scale group communication. In order to address the performance concerns, there have been efforts to account for limited access link bandwidth at the end-system devices while constructing the forwarding overlay paths.
These efforts, however, do not take into account the “last-mile” problem in terms of the contentions and the asymmetry. Indeed, the supply of Internet backbone bandwidth has kept pace with (and often surpassed) increasing demand, while the “last mile” bandwidth available to residences and small businesses remains a severe limitation. With the advent of WDM (Wavelength Division Multiplexing) technologies, this problem will only become more stringent. Last-mile connections, e.g., cable modems, DSL (digital subscriber line), ISDN (integrated services digital network), and telephone modems, form the bandwidth and latency bottlenecks in connecting the vast majority of home users to the Internet.
End-system multicast networks are especially dependent on last-mile connections, since they require that data traverse these last-mile bottlenecks at each forwarding step. This is especially true of uplink capacity, since even the fastest downstream technologies (DSL and cable modems) have far less upstream capacity. When end-system multicast is deployed, this upstream capacity bottleneck scenario results in significant contention on the bottleneck link, with multiple connections vying for their share of the bandwidth.
End-system multicast relies on forwarding nodes, which receive data, replicate it, and transmit it to multiple receivers. This requires several times more upstream bandwidth than downstream, further exaggerating the already asymmetric nature of many last-mile links. As a result, packets may arrive at an end system much faster than it is capable of forwarding the replicated copies, causing them to queue up in the operating system and/or network interface buffers.
Several efforts have proposed algorithms for the construction of overlays optimized for simple end-to-end delay and bandwidth metrics. Various efforts [1], [2], [3] address the construction of overlays to bound the delay while maximizing the bandwidth. In order to address the QoS concerns, there have been efforts [4], [5], [2], [3] to account for limited access link bandwidth at the end-system devices while constructing the forwarding overlay paths. Various graph theoretic algorithms [1], [2], [3] have been proposed to bound the end-to-end delay while accounting for bandwidth limitations at each forwarding node. The efforts that have focused on QoS based overlay design have either focused on delay or bandwidth as the service requirement.
There are many applications, however, that are elastic in that they can tolerate some amount of loss as well as delay. Chu et al. [6] is one of the first efforts to propose overlay network based mechanisms for supporting collaborative video conferencing applications accounting for both bandwidth and delay requirements. Adapting their previous efforts [1], Chu et al. proposes an algorithm for constructing an overlay tree that assigns priority to bandwidth requirements over the delay requirements in the construction of the overlay forwarding tree. [6] proposes overlay construction among a set of forwarding servers in a two-tier architecture for minimizing the average delay. [4], [5], [7], [2] are steps in the direction that propose intelligent overlay construction accounting for application requirements. These efforts, however, do not explicitly account for the queuing delays caused by contention for last mile bandwidth bottlenecks and sharing of this last mile with link asymmetry. These issues influence the outcome of the constructed overlay as the available bandwidth for each forwarding link is dependent on the node forwarding fanout.
In view of the foregoing, a need has been recognized in connection with overcoming the shortcomings and disadvantages presented by conventional arrangements.